package org.lql.algo.codecrush.hot100.heap;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author: liangqinglong
 * @date: 2025-09-27 21:26
 * @description: 347. 前 K 个高频元素 <a href="https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class TopKFrequent {

	public int[] topKFrequent(int[] nums, int k) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int num : nums) {
			map.put(num, map.getOrDefault(num, 0) + 1);
		}
		PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			queue.offer(new int[]{entry.getKey(), entry.getValue()});
			if (queue.size() > k) {
				queue.poll();
			}
		}

		int[] res = new int[k];
		for (int i = 0; i < k; i++) {
			res[i] = queue.poll()[0];
		}
		return res;
	}

	public static void main(String[] args) {
		int[] nums = {1, 1, 1, 2, 2, 3};
		int k = 2;
		System.out.println(Arrays.toString(new TopKFrequent().topKFrequent(nums, k)));
	}
}
